package com.ljy.kotlindemo.leetcode;

/**
 * @Author: LiuJinYang
 * @CreateDate: 2021/7/16
 * @Description:
 */
public class QuickUnionFind {
    private int[] roots;
    public QuickUnionFind(int n){
        roots=new int[n];
        for (int i = 0; i < n; i++) {
            roots[i]=i;
        }
    }
    private int findRoot(int i){
        int root=i;
        while (root!=roots[root]) {
            root=roots[root];
        }
        while (i!=roots[i]){
            int temp=roots[i];
            roots[i]=root;
            i=temp;
        }
        return root;
    }

    public boolean connect(int p,int q){
        return findRoot(p)==findRoot(q);
    }

    public void union(int p,int q){
        int qroot=findRoot(q);
        int proot=findRoot(p);
        roots[proot]=qroot;
    }
}
